import LinkedList from './linked-list';
import { DoublyNode } from './models/linked-list-models';
import { IEqualsFunction, defaultEquals } from '../util';
/**
 * 双向链表是一个特殊的链表。
 * 区别就是它的数据元素由一个存储元素本身的节点、一个指向下一个元素的引用、
 * 一个指向上一个元素的引用组成的。也就是说双向链表双向的，而普通链表是单向的。
 */
export default class DoublyLinkedList<T> extends LinkedList<T> {
    protected head: DoublyNode<T> | undefined;
    protected tail: DoublyNode<T> | undefined;
    constructor(equalsFn: IEqualsFunction<T> = defaultEquals) {
        super(equalsFn);
    }
    /**
     * 向链表尾部添加元素
     */
    public push(element: T) {
        const doublyNode = new DoublyNode<T>(element);
        if (this.head == null) { // 链表为空
            this.tail = this.head = doublyNode; // 直接赋值给head和tail
        } else {
            doublyNode.next = this.tail.next; // 优化，方便形成循环链表
            this.tail.next = doublyNode;
            doublyNode.prev = this.tail; // 将新元素与最后一个元素tail连接起来
            this.tail = doublyNode;
        }
        this.count ++; // 数量更新
    }
    /**
     * 向链表首部添加元素
     */
    public unshift(element: T) {
        const doublyNode = new DoublyNode<T>(element);
        if (this.head == null) { // 链表为空
            this.tail = this.head = doublyNode; // 直接赋值给head和tail
        } else {
            doublyNode.prev = this.head.prev; // 优化，方便形成循环链表
            this.head.prev = doublyNode;
            doublyNode.next = this.head; // 将新元素与第一个元素head连接起来
            this.head = doublyNode;
        }
        this.count ++; // 数量更新
    }
    /**
     * 在任意位置插入新元素
     */
    public insert(element: T, position: number): boolean {
        if (position < 0 || position > this.count) {
            return false;
        }
        if (position === 0) {
            this.unshift(element);
        } else if (position === this.count) {
            this.push(element);
        } else {
            const doublyNode: DoublyNode<T> = new DoublyNode<T>(element);
            const current: DoublyNode<T> = this.getElementAt(position - 1);
            doublyNode.next = current.next; // 指针变更，画图去理解吧
            doublyNode.next.prev = doublyNode;
            doublyNode.prev = current;
            doublyNode.prev.next = doublyNode;
            this.count ++; // 数量更新
        }
        return true;
    }
    /**
     * 从双向链表中移除指定位置的元素
     */
    public removeAt(index: number): T {
        if (this.isEmpty() || index < 0 || index >= this.count) {
            return undefined;
        }
        let result: DoublyNode<T> = null;
        if (this.count === 1) { // 特殊情况1：双向链表只有一个元素
            result = this.head;
            this.clear();
            return result.element;
        }
        if (index === 0) { // 特殊情况2：要删除双向链表首部元素
            result = this.head; // 先临时保存
            this.head = this.head.next; // 更新head
            this.head.prev = undefined; // 新head的prev肯定是undefined
        } else if (index === (this.count - 1)) { // 特殊情况3：要删除双向链表尾部元素(这里区别于单向链表要考虑尾部)
            result = this.tail; // 先临时保存
            this.tail = this.tail.prev; // 更新tail
            this.tail.next = undefined; // 新head的prev肯定是undefined
        } else {
            result = this.getElementAt(index);
            result.prev.next = result.next; // 引用变更，去掉result
            result.next.prev = result.prev; // 引用变更，去掉result
        }
        result.next = undefined;
        result.prev = undefined;
        this.count --; // 数量更新
        return result.element;
    }
    /**
     * 返回元素在链表中的索引
     */
    public indexOf(element: T): number {
        // 优化，使用size，因为要考虑循环链表
        for (let i = 0, node = this.head; i < this.size() && node != null; i ++, node = node.next) {
            if (this.equalsFn(element, node.element)) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 从链表中移除指定元素
     */
    public remove(element: T): T {
        const index: number = this.indexOf(element);
        return this.removeAt(index);
    }
    /**
     * 返回链表中的尾部元素
     */
    public getTail() {
        return this.tail;
    }
    /**
     * 返回链表中的首部元素
     */
    public getHead() {
        return this.head;
    }
    /**
     * 清空
     */
    public clear() {
        super.clear();
        this.tail = undefined;
    }
    /**
     * 返回链表的字符串展示
     */
    public toString(): string {
        if (this.isEmpty()) {
            return '';
        }
        let current: DoublyNode<T> = this.head;
        let objString: string = `${current.element}`;
        for (let i = 1; i < this.size(); i ++) {
            current = current.next;
            objString = `${objString},${current.element}`;
        }
        return objString;
    }
    /**
     * 反序返回链表的字符串展示
     */
    public inverseToString() {
        if (this.isEmpty()) {
            return '';
        }
        let current: DoublyNode<T> = this.tail;
        let objString: string = `${current.element}`;
        for (let i = 1; i < this.size(); i ++) {
            current = current.prev;
            objString = `${objString},${current.element}`;
        }
        return objString;
    }
}
